/**
 @Author:          Yotam Hakim
  Create Date:     28/07/2010
  Last Modified:   04/08/2010
 @Brief:           binary tree ADT (Iterator version)
**/

#ifndef __TREEITER_H__
#define __TREEITER_H__

typedef struct Tree_t Tree;
typedef struct TreeIter_t* TreeIter;


typedef int(*Less_f)(void* elmn1, void* elmn2);

/*user must supply a 'less' function which determines which of two  tree elements is SMALLER :

    return value:
    1 for true  (elmn1 < elmn2)
    0 otherwise

    example : compare two "persons" structures by their age field.

    struct person_t
    {
        char *name;
        int age;
    }

    int AgeIsSmaller (void* elmn1, void* elmn2);
    {
        return ((person_t*)(elmn1))->age < ((person*)(elmn2))->age;
    }

    The calling squence may be :

    struct person_t yosi,rita;
    less Func = AgeIsSmaller;
    strcpy(yosi.name, "Yosi");      strcpy(rita.name, "Rita");
    yosi.age = 55;                  rita.age = 54;

    bool = AgeIsSmaller(rita,yosi) ;   // which returns, in this case, true.

*/


/*create a new tree data structure.
input : user defind less function (defined above)
return value
On success : pointer to Tree structure
On error  (due to allocation faliure)  : end iterator
time scaling : const */
Tree* TreeNew(Less_f);

/*Delete whole tree.  time scaling: O(N)*/
void  TreeDel (Tree*);

/*Insert new element into tree.
return value :Iterator to inserted item.
on error return the "end Iterator". errors may be due to allocation faliure.
DO NOT INSERT NULL POINTER!!
time scaling : logN*/
TreeIter  TreeInsert(Tree* ,void* item);

/*find an item on tree
return value. if item found:  Iterator to  item
              no item found:  end Iterator
time scaling:logN */
TreeIter  TreeFind  (Tree*, void* item) ;

/*check if tree is empty time scaling:const return value (boolian) 1 for true 0 for false. */
int TreeIsEmpty(Tree*);

/*extract data from tree time scaling:const */
void* TreeGetData(TreeIter);

/*get "begin Itertor" (refers to smallest tree element). Applying  TreeBegin on an empty tree
returns end Iterator. time scaling:const */
TreeIter TreeBegin(Tree*);

/*gets "end  Itertor" (not valid itetator whose previous is the tree's larget element). time scaling:const */
TreeIter TreeEnd(Tree*);

/*return an Iterator to "next". that is :
  if 3 4 5 1 2 3 were inserted into a tree of integers then :
  2 = next(1) ,3 = next(2) , 3 = next(3) ,4 = next(3)  ect' (this abstract notation not function call)
  time scaling:logN.
  on faliure or when inserting the larget element of tree returns end Iterator*/
TreeIter TreeNext(TreeIter);

/*the oppositve of next. see next documentation*/
TreeIter TreePrev(TreeIter);

/*remove an element from tree  time scaling. do not try to remove endIterator. time scaling:logN
returns next element iterator */
TreeIter TreeRemove(TreeIter);

/*find if two tree elements are equal by their Itertaros. return value boolian*/
int  TreeIsEqual(TreeIter, TreeIter);

#endif /*__TREEITER_H__*/
